﻿#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
#define M 1000000
int NumberOfThree(int arr[], int low, int high);
template <class T>
void Print(T a[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << "[" << a[i] << "]";
	}
	cout << endl;
}
template <class T>
void Swap(T& a, T& b)
{
	T asd;
	asd = a;
	a = b;
	b = asd;
}
template <class T>
int Partition(T a[], int p, int r)
{
	int i = p, j = r + 1;
	T x = NumberOfThree(a, p, r);
	while (true)
	{
		while (a[++i] < x && i < r);
		while (a[--j] > x);
		if (i >= j)break;
		Swap(a[i], a[j]);
	}
	a[p] = a[j];
	a[j] = x;
	return j;
}
void InsertSort(int arr[], int m, int n)
{
	int i, j;
	int temp;
	for (i = m + 1; i <= n; i++)
	{
		temp = arr[i];
		for (j = i - 1; (j >= m) && (arr[j] > temp); j--)
		{
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = temp;
	}
}
int NumberOfThree(int arr[], int low, int high)
{
	int mid = low + ((high - low) >> 1);
		if (arr[mid] > arr[high])
		{
			Swap(arr[mid], arr[high]);
		}
	if (arr[low] > arr[high])
	{
		Swap(arr[low], arr[high]);
	}
	if (arr[mid] > arr[low])
	{
		Swap(arr[mid], arr[low]);
	}
	return arr[low];
}
template <class T>
void QSort(T arr[], int low, int high)
{
	int pivotPos;
	if (high - low + 1 < 10)
	{
		InsertSort(arr, low, high);
		return;
	}
	if (low < high)
	{
		pivotPos = Partition(arr, low, high);
		QSort(arr, low, pivotPos - 1);
		QSort(arr, pivotPos + 1, high);
	}
}
int a[M] = { 0 };
int main()
{
	srand(time(0));
	for (int i = 0; i < M; i++)
		a[i] = rand() % (M);
	clock_t start_time = clock();
	QSort(a, 0, M - 1);
	clock_t end_time = clock();
	cout << "Runing time is:" << static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
	return 0;
}
